
#pragma once

#include <string>
#include <vector>
#include <ctype.h>
#include <algorithm>

using namespace std;

namespace quicks {
	
	struct matchchar {
		wchar_t c;
		bool matches;
	};
	typedef struct matchchar matchchar_t;
	typedef basic_string<matchchar_t, char_traits<matchchar_t>, allocator<matchchar_t> > matchstring;
	// string converter functions
	void MatchStringToWString(const matchstring& ms, wstring& ws);
	void WStringToMatchStringUnMatched(const wstring& ws, matchstring& ms);

	template<class S> 
	struct MatchInput {
		const wstring* str;
		const S* data;
	};
	template<class U> 
	struct MatchOutput {
		matchstring str;
		int score;
		const U* data;
	};
	template<class U>
	bool operator < (const MatchOutput<U>& left, const MatchOutput<U>& right) { 
		return (left.score > right.score);
	}
	
	template<class T> 
	class IdoComplete {
	public:
		IdoComplete() {}
		~IdoComplete() {}
		typedef MatchOutput<T> Match;
		typedef vector<Match> MatchVector;
		struct MatchResult {
			wstring hint;
			MatchVector matches;
		};

		void MatchInput(MatchResult& result, const wstring& key, const vector<MatchInput<T>>& haystack) {

			result.matches.clear();
			result.hint.clear();
			if (key.size() > 0) {
				for (unsigned int i = 0; i < haystack.size(); i++) {
					MatchOutput<T> mo;
					mo.data = haystack[i].data;
					mo.score = InnerMatch(mo.str, key, *(haystack[i].str), 0, 0, 0);
					if (mo.score > 0) {
						result.matches.push_back(mo);
					}
				}
				// use stable sort here so that the more recent ones stay more recent, depending on relevance
				stable_sort(result.matches.begin(), result.matches.end()); 

				// find largest common substring after key[xxx]
				int nLeastLen = 0xffffff;
				bool bMatchedAll = true;
				bool bHintInitialized = false;
				for (unsigned int i = 0; i < result.matches.size() && bMatchedAll; i++) {
					bool bMatchedThis = false;
					unsigned int k = 0;
					// find the beginning of each match
					for (; k < result.matches[i].str.size(); k++) {
						// 1. match the original key
						unsigned int j = 0;
						for (; j < key.size(); j++) {
							if ( towlower(key[j]) != towlower(result.matches[i].str[k+j].c) )
								break;
						}
						// 2. if we matched the key, match whatever we have for the hint
						if (j == key.size()) {
							bMatchedThis = true;
							if (bHintInitialized) {
								unsigned int l = 0;
								for (; l < result.hint.size(); l++) {
									if ( towlower(result.hint[l]) != towlower(result.matches[i].str[k+j+l].c) )
										break;
								}
								result.hint = result.hint.substr(0, l); // second param is length
							} else {
								bHintInitialized = true;
								MatchStringToWString(result.matches[i].str.substr(k+j), result.hint);
							}
						}
					}
					bMatchedAll &= bMatchedThis;
				}
			} else {
				for (unsigned int i = 0; i < haystack.size(); i++) {
					MatchOutput<T> mo;
					mo.data = haystack[i].data;
					WStringToMatchStringUnMatched(*(haystack[i].str), mo.str);
					result.matches.push_back(mo);
				}
			}
		}

		static int InnerMatch(matchstring& match, const wstring& key, const wstring& hole, int i, int j, int streak) {
			// if we ate the key before the whole, then score > 0
			if (key.size() == i) {
				// need to copy the rest of the hole to the match.
				for (unsigned int k = j; k < hole.size(); k++) {
					matchchar c;
					c.c = hole[k];
					c.matches = false;
					match.push_back(c);
				}
				return streak;
			}
			// if we ate the hole before the key, then score = 0
			if (hole.size() == j)
				return 0;

			// if this character matches, take the max of using the key here,
			// or using it later.

			matchchar c;
			c.c = hole[j];

			if (towlower(key[i]) == towlower(hole[j])) {

				// match them, eat both
				matchstring m1;
				int s1 = InnerMatch(m1, key, hole, i + 1, j + 1, streak + 1);
				// no match, move on
				matchstring m2;
				int s2 = InnerMatch(m2, key, hole, i, j + 1, 0);
				if (s1 >= s2) {
					// matching was better
					c.matches = true;
					match.push_back(c);
					match.append(m1);
					return s1;
				} else {
					// not matching was better
					c.matches = false;
					match.push_back(c);
					match.append(m2);
					return s2;
				}
			}
			// no match, move on
			c.matches = false;
			match.push_back(c);
			return InnerMatch(match, key, hole, i, j + 1, 0);
			
		}
	private:
		TCHAR** m_mat;
		static const int MAXSIZE = 1024;
	};

}

